{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Ways to Make a Fair Array"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #dynamic-programming"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #动态规划"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: waysToMakeFair"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #生成平衡数组的方案数"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个整数数组 <code>nums</code> 。你需要选择 <strong>恰好</strong> 一个下标（下标从 <strong>0</strong> 开始）并删除对应的元素。请注意剩下元素的下标可能会因为删除操作而发生改变。</p>\n",
    "\n",
    "<p>比方说，如果 <code>nums = [6,1,7,4,1]</code> ，那么：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>选择删除下标 <code>1</code> ，剩下的数组为 <code>nums = [6,7,4,1]</code> 。</li>\n",
    "\t<li>选择删除下标 <code>2</code> ，剩下的数组为 <code>nums = [6,1,4,1]</code> 。</li>\n",
    "\t<li>选择删除下标 <code>4</code> ，剩下的数组为 <code>nums = [6,1,7,4]</code> 。</li>\n",
    "</ul>\n",
    "\n",
    "<p>如果一个数组满足奇数下标元素的和与偶数下标元素的和相等，该数组就是一个 <strong>平衡数组</strong> 。</p>\n",
    "\n",
    "<p>请你返回删除操作后，剩下的数组<em> </em><code>nums</code><em> </em>是 <strong>平衡数组</strong> 的 <strong>方案数</strong> 。</p>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>nums = [2,1,6,4]\n",
    "<b>输出：</b>1\n",
    "<strong>解释：</strong>\n",
    "删除下标 0 ：[1,6,4] -> 偶数元素下标为：1 + 4 = 5 。奇数元素下标为：6 。不平衡。\n",
    "删除下标 1 ：[2,6,4] -> 偶数元素下标为：2 + 4 = 6 。奇数元素下标为：6 。平衡。\n",
    "删除下标 2 ：[2,1,4] -> 偶数元素下标为：2 + 4 = 6 。奇数元素下标为：1 。不平衡。\n",
    "删除下标 3 ：[2,1,6] -> 偶数元素下标为：2 + 6 = 8 。奇数元素下标为：1 。不平衡。\n",
    "只有一种让剩余数组成为平衡数组的方案。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>nums = [1,1,1]\n",
    "<b>输出：</b>3\n",
    "<b>解释：</b>你可以删除任意元素，剩余数组都是平衡数组。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>nums = [1,2,3]\n",
    "<b>输出：</b>0\n",
    "<b>解释：</b>不管删除哪个元素，剩下数组都不是平衡数组。\n",
    "</pre>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 <= nums.length <= 10<sup>5</sup></code></li>\n",
    "\t<li><code>1 <= nums[i] <= 10<sup>4</sup></code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [ways-to-make-a-fair-array](https://leetcode.cn/problems/ways-to-make-a-fair-array/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [ways-to-make-a-fair-array](https://leetcode.cn/problems/ways-to-make-a-fair-array/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[2,1,6,4]', '[1,1,1]', '[1,2,3]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def waysToMakeFair(self, nums: List[int]) -> int:\n",
    "        res = odd1 = even1 = odd2 = even2 = 0\n",
    "        for i, num in enumerate(nums):\n",
    "            if i & 1:\n",
    "                odd2 += num\n",
    "            else:\n",
    "                even2 += num\n",
    "        for i, num in enumerate(nums):\n",
    "            if i & 1:\n",
    "                odd2 -= num\n",
    "            else:\n",
    "                even2 -= num\n",
    "            if odd1 + even2 == odd2 + even1:\n",
    "                res += 1\n",
    "            if i & 1:\n",
    "                odd1 += num\n",
    "            else:\n",
    "                even1 += num\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def waysToMakeFair(self, nums: List[int]) -> int:\n",
    "        ans = s = 0\n",
    "        for i, x in enumerate(nums):\n",
    "            s += x if i & 1 else -x\n",
    "        for i, x in enumerate(nums):\n",
    "            s -= x if i & 1 else -x\n",
    "            ans += s == 0\n",
    "            s -= x if i & 1 else -x\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def waysToMakeFair(self, nums: List[int]) -> int:\n",
    "        ret = s = 0\n",
    "        for i, num in enumerate(nums):\n",
    "            s += num if i % 2 == 0 else -num\n",
    "        for i, num in enumerate(nums):\n",
    "            s -= num if i % 2 == 0 else -num\n",
    "            ret += s == 0\n",
    "            s -= num if i % 2 == 0 else -num\n",
    "        return ret\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def waysToMakeFair(self, nums: List[int]) -> int:\n",
    "        res = odd1 = odd2 = even1 = even2 = 0\n",
    "        for i, num in enumerate(nums):\n",
    "            if i & 1:\n",
    "                odd2 += num\n",
    "            else:\n",
    "                even2 += num\n",
    "        for i, num in enumerate(nums):\n",
    "            if i & 1:\n",
    "                odd2 -= num\n",
    "            else:\n",
    "                even2 -= num\n",
    "            if odd1 + even2 == odd2 + even1:\n",
    "                res += 1\n",
    "            if i & 1:\n",
    "                odd1 += num\n",
    "            else:\n",
    "                even1 += num\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def waysToMakeFair(self, nums: List[int]) -> int:\n",
    "        even, odd = 0, 0\n",
    "        for i in range(0, len(nums), 2):\n",
    "            even += nums[i]\n",
    "        for j in range(1, len(nums), 2):\n",
    "            odd += nums[j]\n",
    "        even_, odd_ = 0, 0\n",
    "        flag = len(nums) % 2 == 1\n",
    "        r = 0\n",
    "        for ele in nums[::-1]:\n",
    "            if flag:\n",
    "                even -= ele\n",
    "                if even + odd_ == odd + even_:\n",
    "                    r += 1\n",
    "                even_ += ele\n",
    "            else:\n",
    "                odd -= ele\n",
    "                if even + odd_ == odd + even_:\n",
    "                    r += 1\n",
    "                odd_ += ele\n",
    "            flag = not flag\n",
    "        return r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def waysToMakeFair(self, nums: List[int]) -> int:\n",
    "       n = len(nums)\n",
    "       even = sum(nums[i] for i in range(0, n, 2))\n",
    "       odd = sum(nums) - even\n",
    "       res = 0\n",
    "       curEven = 0\n",
    "       curOdd = 0\n",
    "       for i in range(n):\n",
    "          if i % 2 == 0:\n",
    "             if curEven + odd == curOdd + even - nums[i]:\n",
    "                res += 1\n",
    "             curEven += nums[i]\n",
    "             even -= nums[i]\n",
    "          else:\n",
    "             if curOdd + even == curEven + odd - nums[i]:\n",
    "                res += 1\n",
    "             curOdd += nums[i]\n",
    "             odd -= nums[i]\n",
    "       return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def waysToMakeFair(self, nums: List[int]) -> int:\n",
    "        res = odd1 = even1 = odd2 = even2 = 0\n",
    "        for i, num in enumerate(nums):\n",
    "            if i & 1:\n",
    "                odd2 += num\n",
    "            else:\n",
    "                even2 += num\n",
    "        for i, num in enumerate(nums):\n",
    "            if i & 1:\n",
    "                odd2 -= num\n",
    "            else:\n",
    "                even2 -= num\n",
    "            if odd1 + even2 == odd2 + even1:\n",
    "                res += 1\n",
    "            if i & 1:\n",
    "                odd1 += num\n",
    "            else:\n",
    "                even1 += num\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def waysToMakeFair(self, nums: List[int]) -> int:\n",
    "        ### 初始化参数，前奇偶为0，后奇偶分别记录数组奇偶的和\n",
    "        front_ji = 0\n",
    "        front_ou = 0\n",
    "        last_ji = 0\n",
    "        last_ou = 0\n",
    "        lenthn = len(nums)\n",
    "        for i in range(lenthn):\n",
    "            if i % 2 == 0:\n",
    "                last_ou += nums[i]\n",
    "            else:\n",
    "                last_ji += nums[i]\n",
    "        ### 计算平衡数组\n",
    "        res = 0\n",
    "        for j in range(lenthn):\n",
    "            if j % 2 == 0:\n",
    "                last_ou = last_ou - nums[j]\n",
    "                if last_ou + front_ji == last_ji + front_ou:\n",
    "                    res += 1\n",
    "                front_ou += nums[j]\n",
    "            else:\n",
    "                last_ji = last_ji - nums[j]\n",
    "                if last_ji + front_ou == last_ou + front_ji:\n",
    "                    res += 1\n",
    "                front_ji += nums[j]\n",
    "        return res\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def waysToMakeFair(self, nums: List[int]) -> int:\n",
    "        s=sum(v if i&1 else -v for i,v in enumerate(nums))\n",
    "        ans,curr=0,0\n",
    "        for i,v in enumerate(nums):\n",
    "            if 2*curr+s==(v if i&1 else -v):\n",
    "                ans+=1\n",
    "            curr+=-v if i&1 else v\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def waysToMakeFair(self, nums: List[int]) -> int:\n",
    "        res = odd1 = even1 = odd2 = even2 = 0\n",
    "        for i, num in enumerate(nums):\n",
    "            if i & 1:\n",
    "                odd2 += num\n",
    "            else:\n",
    "                even2 += num\n",
    "        for i, num in enumerate(nums):\n",
    "            if i & 1:\n",
    "                odd2 -= num\n",
    "            else:\n",
    "                even2 -= num\n",
    "            if odd1 + even2 == odd2 + even1:\n",
    "                res += 1\n",
    "            if i & 1:\n",
    "                odd1 += num\n",
    "            else:\n",
    "                even1 += num\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def waysToMakeFair(self, nums: List[int]) -> int:\n",
    "\n",
    "        f = True\n",
    "        s1 = 0\n",
    "        s2 = 0\n",
    "        for num in nums:\n",
    "            if f:\n",
    "                s1 += num\n",
    "                f = False\n",
    "            else:\n",
    "                s2 += num\n",
    "                f = True\n",
    "        t1 = 0\n",
    "        t2 = 0\n",
    "\n",
    "        ans = 0\n",
    "        f = True\n",
    "        for num in nums:\n",
    "            if f:\n",
    "                s1 -= num\n",
    "                if t1 + s2 == t2 + s1:\n",
    "                    ans += 1\n",
    "                t1 += num\n",
    "                f = False\n",
    "            else:\n",
    "                s2 -= num\n",
    "                if t1 + s2 == t2 + s1:\n",
    "                    ans += 1\n",
    "                t2 += num\n",
    "                f = True\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def waysToMakeFair(self, nums: List[int]) -> int:\n",
    "        oddl, evenl, oddr, evenr, ans = 0, 0, 0, 0, 0\n",
    "        for i, x in enumerate(nums):\n",
    "            if i & 1: oddl += x\n",
    "            else : evenl += x\n",
    "        for i in range(len(nums) - 1, -1, -1):\n",
    "            if i & 1: oddl -= nums[i]\n",
    "            else : evenl -= nums[i]\n",
    "            if oddl + evenr == evenl + oddr: ans += 1\n",
    "            if i & 1: oddr += nums[i]\n",
    "            else : evenr += nums[i]\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def waysToMakeFair(self, nums: List[int]) -> int:\n",
    "        res = 0\n",
    "        pre_odd = pre_even = 0\n",
    "        post_odd = sum(nums[1::2])\n",
    "        post_even = sum(nums[2::2])\n",
    "\n",
    "        for i, num in enumerate(nums):\n",
    "            if pre_odd + post_even == pre_even + post_odd:\n",
    "                res += 1\n",
    "            if i+1 < len(nums):\n",
    "                if i % 2 == 0:\n",
    "                    pre_even += num\n",
    "                    post_odd -= nums[i+1]\n",
    "                else:\n",
    "                    pre_odd += num\n",
    "                    post_even -= nums[i+1]\n",
    "\n",
    "        return res\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def waysToMakeFair(self, nums: List[int]) -> int:\n",
    "      n = len(nums)\n",
    "      odd1 = odd2 = even1 = even2 = 0\n",
    "      for i, num in enumerate(nums):\n",
    "        if i & 1:   odd2 += num\n",
    "        else:       even2 += num\n",
    "      \n",
    "      cnt = 0\n",
    "      for i, num in enumerate(nums):\n",
    "        if i & 1:   odd2 -= num\n",
    "        else:       even2 -= num\n",
    "\n",
    "        if odd1 + even2 == odd2 + even1:\n",
    "          cnt += 1\n",
    "        if i & 1:   odd1 += num\n",
    "        else:       even1 += num\n",
    "      return cnt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def waysToMakeFair(self, nums: List[int]) -> int:\n",
    "        allEven = sum(nums[::2])\n",
    "        allOdd = sum(nums[1::2])\n",
    "        # print(allEven, allOdd)\n",
    "        ans = 0\n",
    "        localEven = 0\n",
    "        localOdd = 0\n",
    "        for idx, num in enumerate(nums):\n",
    "            if idx % 2 == 0:\n",
    "                if allEven - num - localEven + localOdd == allOdd - localOdd + localEven:\n",
    "                    ans+=1\n",
    "            else:\n",
    "                if allEven - localEven + localOdd == allOdd - localOdd + localEven - num:\n",
    "                    ans+=1\n",
    "            if idx % 2 == 0:\n",
    "                localEven += num\n",
    "            else:\n",
    "                localOdd += num\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def waysToMakeFair(self, nums: List[int]) -> int:\n",
    "        # prefix_odd=[0]\n",
    "        # prefix_even=[0]\n",
    "        # pre_odd=0\n",
    "        # pre_even=0\n",
    "        # for i,x in enumerate(nums):\n",
    "        #     if i%2==1:\n",
    "        #         pre_odd+=x\n",
    "        #         prefix_odd.append(pre_odd)\n",
    "        #     else:\n",
    "        #         pre_even+=x\n",
    "        #         prefix_even.append(pre_even)\n",
    "        # # print(prefix_even, prefix_odd)\n",
    "        # n=len(nums)\n",
    "        # res=0\n",
    "        # for i in range(n):\n",
    "        #     ind=i//2+1\n",
    "        #     if i%2==0:\n",
    "        #         evensum = prefix_even[ind-1]+prefix_odd[-1]-prefix_odd[ind-1]\n",
    "        #         oddsum = prefix_odd[ind-1]+prefix_even[-1]-prefix_even[ind]    \n",
    "        #     else:\n",
    "        #         evensum = prefix_even[ind]+prefix_odd[-1]-prefix_odd[ind]\n",
    "        #         oddsum = prefix_odd[ind-1]+prefix_even[-1]-prefix_even[ind]\n",
    "                \n",
    "        #     # print(i,ind,evensum,oddsum)\n",
    "        #     res+=int(evensum==oddsum)\n",
    "        # return res\n",
    "        even_sum = sum(nums[::2])\n",
    "        odd_sum = sum(nums[1::2])\n",
    "        is_even = True\n",
    "        res = 0\n",
    "        pre_even = 0\n",
    "        pre_odd = 0\n",
    "        for x in nums:\n",
    "            if is_even:\n",
    "                even_sum-=x\n",
    "                res += int(pre_even+odd_sum==pre_odd+even_sum)\n",
    "                pre_even+=x\n",
    "            else:\n",
    "                odd_sum-=x\n",
    "                res += int(pre_even+odd_sum==pre_odd+even_sum)\n",
    "                pre_odd += x\n",
    "            is_even = not is_even\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def waysToMakeFair(self, nums: List[int]) -> int:\n",
    "        s1, s2 = sum(nums[::2]), sum(nums[1::2])\n",
    "        ans = t1 = t2 = 0\n",
    "        for i, v in enumerate(nums):\n",
    "            ans += i % 2 == 0 and t2 + s1 - t1 - v == t1 + s2 - t2\n",
    "            ans += i % 2 == 1 and t2 + s1 - t1 == t1 + s2 - t2 - v\n",
    "            t1 += v if i % 2 == 0 else 0\n",
    "            t2 += v if i % 2 == 1 else 0\n",
    "        return ans\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def waysToMakeFair(self, nums: List[int]) -> int:\r\n",
    "        odd = sum(nums[::2])\r\n",
    "        even = sum(nums[1::2])\r\n",
    "        n = len(nums)\r\n",
    "        # 如果删除的位置是偶数，那么奇数下标的和不变，偶数下标的和减去删除的数\r\n",
    "        # 如果删除的位置是奇数，那么偶数下标的和不变，奇数下标的和减去删除的数\r\n",
    "        ans = 0\r\n",
    "        for i in range(n):\r\n",
    "            if i % 2 == 0:\r\n",
    "                odd -= nums[i]\r\n",
    "            else:\r\n",
    "                even -= nums[i]\r\n",
    "            if odd == even:\r\n",
    "                ans += 1\r\n",
    "            if i % 2 == 0:\r\n",
    "                even += nums[i]\r\n",
    "            else:\r\n",
    "                odd += nums[i]\r\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def waysToMakeFair(self, nums: List[int]) -> int:\n",
    "        allEven = sum(nums[::2])\n",
    "        allOdd = sum(nums[1::2])\n",
    "        ans = 0\n",
    "        localEven = 0\n",
    "        localOdd = 0\n",
    "        for idx, num in enumerate(nums):\n",
    "            if idx % 2 == 0:\n",
    "                if allEven - num - localEven + localOdd == allOdd - localOdd + localEven:\n",
    "                    ans+=1\n",
    "                localEven += num\n",
    "            else:\n",
    "                if allEven - localEven + localOdd == allOdd - localOdd + localEven - num:\n",
    "                    ans+=1\n",
    "                localOdd += num         \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def waysToMakeFair(self, nums: List[int]) -> int:\n",
    "        res = odd1 = even1 = 0\n",
    "        odd2, even2 = sum(nums[0::2]), sum(nums[1::2])\n",
    "        for i, num in enumerate(nums):\n",
    "            if i & 1:\n",
    "                even2 -= num\n",
    "            else:\n",
    "                odd2 -= num\n",
    "            if odd1 + even2 == even1 + odd2:\n",
    "                res += 1\n",
    "            if i & 1:\n",
    "                even1 += num\n",
    "            else:\n",
    "                odd1 += num\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def waysToMakeFair(self, nums: List[int]) -> int:\n",
    "        allEven = sum(nums[::2])\n",
    "        allOdd = sum(nums[1::2])\n",
    "        ans = 0\n",
    "        localEven = 0\n",
    "        localOdd = 0\n",
    "        for idx, num in enumerate(nums):\n",
    "            if idx % 2 == 0:\n",
    "                if allEven - num - localEven + localOdd == allOdd - localOdd + localEven:\n",
    "                    ans+=1\n",
    "                localEven += num\n",
    "            else:\n",
    "                if allEven - localEven + localOdd == allOdd - localOdd + localEven - num:\n",
    "                    ans+=1\n",
    "                localOdd += num         \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def waysToMakeFair(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        dp0 = 0\n",
    "        dp1 = 0\n",
    "        dp2 = sum(nums[1::2])\n",
    "        dp3 = sum(nums[2::2])\n",
    "        ans = 0\n",
    "        if dp2 == dp3: ans += 1\n",
    "        for i in range(1, n):\n",
    "            if (i-1) % 2 == 1:\n",
    "                dp0 = dp0\n",
    "                dp1 = dp1 + nums[i-1]\n",
    "                x = dp2\n",
    "                dp2 = dp3\n",
    "                dp3 = x - nums[i]\n",
    "                if dp0 + dp2 == dp1 + dp3:\n",
    "                    ans += 1\n",
    "            else:\n",
    "                dp0 = dp0 + nums[i-1]\n",
    "                dp1 = dp1\n",
    "                x = dp2\n",
    "                dp2 = dp3\n",
    "                dp3 = x - nums[i]\n",
    "                if dp0 + dp3 == dp1 + dp2:\n",
    "                    ans += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def waysToMakeFair(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        s = [0] * (n + 1)\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            s[i] = s[i + 1] + (-1) ** i * nums[i]\n",
    "        acc = 0\n",
    "        res = 0\n",
    "        for i in range(n):\n",
    "            if acc == s[i + 1]:\n",
    "                res += 1\n",
    "            acc += (-1) ** i * nums[i]\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def waysToMakeFair(self, nums: List[int]) -> int:\n",
    "        s1, s2 = sum(nums[::2]), sum(nums[1::2])\n",
    "        ans = t1 = t2 = 0\n",
    "        for i, v in enumerate(nums):\n",
    "            ans += i % 2 == 0 and t2 + s1 - t1 - v == t1 + s2 - t2\n",
    "            ans += i % 2 == 1 and t2 + s1 - t1 == t1 + s2 - t2 - v\n",
    "            t1 += v if i % 2 == 0 else 0\n",
    "            t2 += v if i % 2 == 1 else 0\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def waysToMakeFair(self, nums: List[int]) -> int:\n",
    "        s1, s2 = sum(nums[::2]), sum(nums[1::2])\n",
    "        ans = t1 = t2 = 0\n",
    "        for i, v in enumerate(nums):\n",
    "            ans += i % 2 == 0 and t2 + s1 - t1 - v == t1 + s2 - t2\n",
    "            ans += i % 2 == 1 and t2 + s1 - t1 == t1 + s2 - t2 - v\n",
    "            t1 += v if i % 2 == 0 else 0\n",
    "            t2 += v if i % 2 == 1 else 0\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def waysToMakeFair(self, nums: List[int]) -> int:\n",
    "        even = sum(nums[::2])\n",
    "        odd = sum(nums[1::2])\n",
    "        # print(even,odd)\n",
    "        preeven = 0\n",
    "        preodd =0\n",
    "        res = 0\n",
    "        for i,x in enumerate(nums):\n",
    "            if i%2==0:\n",
    "                even-=x\n",
    "            else:\n",
    "                odd-=x\n",
    "            if preodd+even==preeven+odd:\n",
    "                res +=1\n",
    "            if i%2==0:\n",
    "                preeven+=x\n",
    "            else:\n",
    "                preodd+=x\n",
    "        return res\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def waysToMakeFair(self, nums: List[int]) -> int:\n",
    "      n = len(nums)\n",
    "      odd1 = odd2 = even1 = even2 = 0\n",
    "      for i, num in enumerate(nums):\n",
    "        if i & 1:   odd2 += num\n",
    "        else:       even2 += num\n",
    "      \n",
    "      cnt = 0\n",
    "      for i, num in enumerate(nums):\n",
    "        if i & 1:   odd2 -= num\n",
    "        else:       even2 -= num\n",
    "\n",
    "        if odd1 + even2 == odd2 + even1:\n",
    "          cnt += 1\n",
    "        if i & 1:   odd1 += num\n",
    "        else:       even1 += num\n",
    "      return cnt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def waysToMakeFair(self, nums: List[int]) -> int:\r\n",
    "        # ans = 0\r\n",
    "        # for n in nums:\r\n",
    "        #     numsSon = nums.remove(n)\r\n",
    "        #     oneNum = 0\r\n",
    "        #     twoNum = 0\r\n",
    "        # length = len(nums)-1\r\n",
    "        s1, s2 = sum(nums[::2]), sum(nums[1::2])\r\n",
    "        ans = t1 = t2 = 0\r\n",
    "        for i, v in enumerate(nums):\r\n",
    "            ans += i % 2 == 0 and t2 + s1 - t1 - v == t1 + s2 - t2\r\n",
    "            ans += i % 2 == 1 and t2 + s1 - t1 == t1 + s2 - t2 - v\r\n",
    "            t1 += v if i % 2 == 0 else 0\r\n",
    "            t2 += v if i % 2 == 1 else 0\r\n",
    "        \r\n",
    "        return ans\r\n",
    "         "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def waysToMakeFair(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        dp = [0] * (n + 1)\n",
    "        for i in range(1, n + 1):\n",
    "            dp[i] = dp[i-1] + (nums[i-1] if i % 2 else -nums[i-1])\n",
    "\n",
    "        ans = 0\n",
    "        for i in range(1, n + 1):\n",
    "            if dp[i - 1] == dp[n] - dp[i]:\n",
    "                ans += 1\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def waysToMakeFair(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        dp = [0] * (n+1)\n",
    "        for i in range(1, n + 1):\n",
    "            dp[i] = dp[i-1] + (nums[i-1] if i % 2 else -nums[i-1])\n",
    "\n",
    "        res = 0\n",
    "        for i in range(1, n + 1):\n",
    "            if dp[i - 1] == dp[n] - dp[i]:\n",
    "                res += 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def waysToMakeFair(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        dp = [0] * (n+1)\n",
    "        for i in range(1, n + 1):\n",
    "            dp[i] = dp[i-1] + (nums[i-1] if i % 2 else -nums[i-1])\n",
    "\n",
    "        res = 0\n",
    "        for i in range(1, n + 1):\n",
    "            if dp[i - 1] == dp[n] - dp[i]:\n",
    "                res += 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def waysToMakeFair(self, nums: List[int]) -> int:\n",
    "        # 后缀奇偶和\n",
    "        n = len(nums)\n",
    "        sum_ = [0] * (n + 2)\n",
    "        odd = even = 0\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            if i & 1:\n",
    "                odd += nums[i]\n",
    "                sum_[i] = odd\n",
    "            else:\n",
    "                even += nums[i]\n",
    "                sum_[i] = even\n",
    "        \n",
    "        ans = 0\n",
    "        # 一个个删除\n",
    "        for i in range(n):\n",
    "            odd2 = odd\n",
    "            even2 = even\n",
    "            if i & 1:\n",
    "                odd2 -= nums[i]\n",
    "                even2 += sum_[i + 2] - sum_[i + 1]\n",
    "                odd2 += sum_[i + 1] - sum_[i + 2]\n",
    "            else:\n",
    "                even2 -= nums[i]\n",
    "                odd2 += sum_[i + 2] - sum_[i + 1]\n",
    "                even2 += sum_[i + 1] - sum_[i + 2]\n",
    "            if even2 == odd2:\n",
    "                ans += 1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def waysToMakeFair(self, nums: List[int]) -> int:\n",
    "        prefix_odd=[0]\n",
    "        prefix_even=[0]\n",
    "        pre_odd=0\n",
    "        pre_even=0\n",
    "        for i,x in enumerate(nums):\n",
    "            if i%2==1:\n",
    "                pre_odd+=x\n",
    "                prefix_odd.append(pre_odd)\n",
    "            else:\n",
    "                pre_even+=x\n",
    "                prefix_even.append(pre_even)\n",
    "        # print(prefix_even, prefix_odd)\n",
    "        n=len(nums)\n",
    "        res=0\n",
    "        for i in range(n):\n",
    "            ind=i//2+1\n",
    "            if i%2==0:\n",
    "                evensum = prefix_even[ind-1]+prefix_odd[-1]-prefix_odd[ind-1]\n",
    "                oddsum = prefix_odd[ind-1]+prefix_even[-1]-prefix_even[ind]    \n",
    "            else:\n",
    "                evensum = prefix_even[ind]+prefix_odd[-1]-prefix_odd[ind]\n",
    "                oddsum = prefix_odd[ind-1]+prefix_even[-1]-prefix_even[ind]\n",
    "                \n",
    "            # print(i,ind,evensum,oddsum)\n",
    "            res+=int(evensum==oddsum)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def waysToMakeFair(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        if not nums:\n",
    "            return 0\n",
    "        dp = [0 for i in range(n)]\n",
    "        dp[0] = nums[0]\n",
    "        count = 0\n",
    "        for i in range(1, n):\n",
    "            dp[i] = dp[i - 1] + (-1) ** i * nums[i]\n",
    "        if dp[n - 1] - dp[0] == 0:\n",
    "            count += 1\n",
    "        for i in range(1, n):\n",
    "            if dp[n - 1] - dp[i] == dp[i - 1]:\n",
    "                count += 1\n",
    "\n",
    "        return count\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def waysToMakeFair(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        if not nums:\n",
    "            return 0\n",
    "        dp = [0 for i in range(n)]\n",
    "        dp[0] = nums[0]\n",
    "        count = 0\n",
    "        for i in range(1, n):\n",
    "            dp[i] = dp[i - 1] + (-1)**i * nums[i]\n",
    "        if dp[n - 1] - dp[0] == 0:\n",
    "            count += 1\n",
    "        for i in range(1, n):\n",
    "            if dp[n - 1] - dp[i] == dp[i - 1]:\n",
    "                count += 1\n",
    "\n",
    "        return count\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def waysToMakeFair(self, nums: List[int]) -> int:\n",
    "        # 后缀奇偶和\n",
    "        n = len(nums)\n",
    "        sum_ = [0] * (n + 2)\n",
    "        odd = even = 0\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            if i & 1:\n",
    "                odd += nums[i]\n",
    "                sum_[i] = odd\n",
    "            else:\n",
    "                even += nums[i]\n",
    "                sum_[i] = even\n",
    "        \n",
    "        ans = 0\n",
    "        # 一个个删除\n",
    "        for i in range(n):\n",
    "            odd2 = odd\n",
    "            even2 = even\n",
    "            if i & 1:\n",
    "                odd2, even2 = even2, odd2\n",
    "\n",
    "            even2 -= nums[i]\n",
    "            odd2 += sum_[i + 2] - sum_[i + 1]\n",
    "            even2 += sum_[i + 1] - sum_[i + 2]\n",
    "            if even2 == odd2:\n",
    "                ans += 1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def waysToMakeFair(self, nums: List[int]) -> int:\n",
    "        # 后缀奇偶和\n",
    "        n = len(nums)\n",
    "        sum_ = [0] * (n + 2)\n",
    "        odd = even = 0\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            if i & 1:\n",
    "                odd += nums[i]\n",
    "                sum_[i] = odd\n",
    "            else:\n",
    "                even += nums[i]\n",
    "                sum_[i] = even\n",
    "        \n",
    "        ans = 0\n",
    "        # 一个个删除\n",
    "        for i in range(n):\n",
    "            odd2 = odd\n",
    "            even2 = even\n",
    "            if i & 1:\n",
    "                odd2, even2 = even2, odd2\n",
    "            if (even2 + 2 * sum_[i + 1] - nums[i]) == (odd2 + 2 * sum_[i + 2]):\n",
    "                ans += 1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def waysToMakeFair(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        odd, even = [0], [0]\n",
    "        ans = 0\n",
    "        for i in range(n):\n",
    "            if i % 2 == 0:\n",
    "                even.append(even[-1] + nums[i])\n",
    "            else:\n",
    "                odd.append(odd[-1] + nums[i])\n",
    "        # print(even, odd)\n",
    "        for i in range(n):\n",
    "            es, os = 0, 0\n",
    "            k = i // 2\n",
    "            if i % 2 == 0:\n",
    "                os = odd[k] + even[-1] - even[k+1]\n",
    "                es = even[k] + odd[-1] - odd[k]\n",
    "            else:\n",
    "                os = odd[k] + even[-1] - even[k+1]\n",
    "                es = even[k+1] + odd[-1] - odd[k+1]\n",
    "            if os == es:\n",
    "                ans += 1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def waysToMakeFair(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        odd, even = [0], [0]\n",
    "        ans = 0\n",
    "        for i in range(n):\n",
    "            if i % 2 == 0:\n",
    "                even.append(even[-1] + nums[i])\n",
    "            else:\n",
    "                odd.append(odd[-1] + nums[i])\n",
    "        # print(even, odd)\n",
    "        for i in range(n):\n",
    "            es, os = 0, 0\n",
    "            k = i // 2\n",
    "            if i % 2 == 0:\n",
    "                os = odd[k] + even[-1] - even[k+1]\n",
    "                es = even[k] + odd[-1] - odd[k]\n",
    "            else:\n",
    "                os = odd[k] + even[-1] - even[k+1]\n",
    "                es = even[k+1] + odd[-1] - odd[k+1]\n",
    "            if os == es:\n",
    "                ans += 1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def waysToMakeFair(self, nums: List[int]) -> int:\n",
    "        oddSum = [0]\n",
    "        evenSum = [0]\n",
    "        for i in range(len(nums)):\n",
    "            if i % 2 == 0:\n",
    "                evenSum.append(evenSum[-1] + nums[i])\n",
    "                oddSum.append(oddSum[-1])\n",
    "            else:\n",
    "                oddSum.append(oddSum[-1] + nums[i])\n",
    "                evenSum.append(evenSum[-1])\n",
    "\n",
    "        res = 0\n",
    "        for i in range(len(nums)):\n",
    "            leftOddSum = oddSum[i]\n",
    "            leftEvenSum = evenSum[i]\n",
    "\n",
    "            rightOddSum = evenSum[-1] - evenSum[i]\n",
    "            rightEvenSum = oddSum[-1] - oddSum[i]\n",
    "            if i % 2 == 0:\n",
    "                rightOddSum -= nums[i]\n",
    "            else:\n",
    "                rightEvenSum -= nums[i]\n",
    "\n",
    "            # print(i, )\n",
    "            if leftEvenSum + rightEvenSum == leftOddSum + rightOddSum:\n",
    "                res += 1\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def waysToMakeFair(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        left2, right2 = [0] * n, [0] * n\n",
    "        for i in range(n):\n",
    "            if i <= 1:\n",
    "                left2[i] = nums[i]\n",
    "            else:\n",
    "                left2[i] = nums[i] + left2[i - 2]\n",
    "\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            if i >= n - 2:\n",
    "                right2[i] = nums[i]\n",
    "            else:\n",
    "                right2[i] = nums[i] + right2[i + 2]\n",
    "        \n",
    "        ans = 0\n",
    "        for i in range(n):\n",
    "            sum0 = (left2[i - 1] if i >= 1 else 0) + (right2[i + 2] if i + 2 < n else 0)\n",
    "            sum1 = (left2[i - 2] if i >= 2 else 0) + (right2[i + 1] if i + 1 < n else 0)\n",
    "            ans += (1 if sum0 == sum1 else 0)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def waysToMakeFair(self, nums: List[int]) -> int:\n",
    "        # 在每个点都知道奇数索引和 偶数索引和\n",
    "        n=len(nums)\n",
    "        pre_odds,pre_evens=[0]*n,[0]*n\n",
    "        suf_odds,suf_evens=[0]*n,[0]*n\n",
    "        odd,even=0,0\n",
    "        for i in range(n):\n",
    "            pre_odds[i]=odd \n",
    "            pre_evens[i]=even\n",
    "            if i%2:\n",
    "                odd+=nums[i]\n",
    "            else:\n",
    "                even+=nums[i]\n",
    "        odd,even=0,0\n",
    "        for i in range(n-1,-1,-1):\n",
    "            suf_odds[i]=odd \n",
    "            suf_evens[i]=even\n",
    "            if i%2:\n",
    "                odd+=nums[i]\n",
    "            else:\n",
    "                even+=nums[i]\n",
    "        # print(pre_odds)\n",
    "        # print(pre_evens)\n",
    "        # print(suf_odds)\n",
    "        # print(suf_evens)\n",
    "        cnt=0\n",
    "        for i in range(n):\n",
    "            if pre_odds[i]+suf_evens[i]==pre_evens[i]+suf_odds[i]:\n",
    "                cnt+=1\n",
    "        return cnt \n",
    "\n",
    "                        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def waysToMakeFair(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        pre_odd = [0]*(n+1)\n",
    "        pre_even = [0]*(n+1)\n",
    "        for i in range(n):\n",
    "            pre_odd[i+1] = pre_odd[i]\n",
    "            pre_even[i+1] = pre_even[i]\n",
    "            if i %2==0:\n",
    "                pre_even[i+1] += nums[i]\n",
    "            else:\n",
    "                pre_odd[i + 1] += nums[i]\n",
    "\n",
    "        post_odd = [0] * (n + 1)\n",
    "        post_even = [0] * (n + 1)\n",
    "        for i in range(n-1, -1, -1):\n",
    "            post_odd[i] = post_odd[i+1]\n",
    "            post_even[i] = post_even[i+1]\n",
    "            if i % 2 == 0:\n",
    "                post_even[i] += nums[i]\n",
    "            else:\n",
    "                post_odd[i] += nums[i]\n",
    "                \n",
    "        ans = 0\n",
    "        for i in range(n):\n",
    "            if i % 2 == 0:\n",
    "                ans += pre_even[i] + post_odd[i+1] == pre_odd[i] + post_even[i+1]\n",
    "            else:\n",
    "                ans += pre_even[i] + post_odd[i + 1] == pre_odd[i] + post_even[i + 1]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def waysToMakeFair(self, nums: List[int]) -> int:\n",
    "      n = len(nums)\n",
    "      prefix = [[0, 0] for _ in range(n+1)]\n",
    "      for i in range(n-1, -1, -1):\n",
    "        prefix[i] = prefix[i+1].copy()\n",
    "        if i % 2: prefix[i][1] += nums[i]\n",
    "        else:     prefix[i][0] += nums[i]\n",
    "      cur = [0, 0]\n",
    "      cnt = 0\n",
    "      for i in range(n):\n",
    "        if cur[0] + prefix[i+1][1] == cur[1] + prefix[i+1][0]:\n",
    "          cnt += 1\n",
    "        if i % 2: cur[1] += nums[i]\n",
    "        else:     cur[0] += nums[i]\n",
    "      return cnt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def waysToMakeFair(self, nums: List[int]) -> int:\n",
    "      n = len(nums)\n",
    "      prefix = [[0, 0] for _ in range(n+1)]\n",
    "      for i in range(n-1, -1, -1):\n",
    "        prefix[i] = prefix[i+1].copy()\n",
    "        if i % 2: prefix[i][1] += nums[i]\n",
    "        else:     prefix[i][0] += nums[i]\n",
    "      cur = [0, 0]\n",
    "      cnt = 0\n",
    "      for i in range(n):\n",
    "        if cur[0] + prefix[i+1][1] == cur[1] + prefix[i+1][0]:\n",
    "          cnt += 1\n",
    "        if i % 2: cur[1] += nums[i]\n",
    "        else:     cur[0] += nums[i]\n",
    "      return cnt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def waysToMakeFair(self, nums: List[int]) -> int:\n",
    "      n = len(nums)\n",
    "      prefix = [[0, 0] for _ in range(n+1)]\n",
    "      for i in range(n-1, -1, -1):\n",
    "        prefix[i] = prefix[i+1].copy()\n",
    "        if i % 2: prefix[i][1] += nums[i]\n",
    "        else:     prefix[i][0] += nums[i]\n",
    "      cur = [0, 0]\n",
    "      cnt = 0\n",
    "      for i in range(n):\n",
    "        if cur[0] + prefix[i+1][1] == cur[1] + prefix[i+1][0]:\n",
    "          cnt += 1\n",
    "        if i % 2: cur[1] += nums[i]\n",
    "        else:     cur[0] += nums[i]\n",
    "      return cnt"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
